This invention relates generally to computer-aided design (CAD) techniques for placement of logic functions and cells on an integrated circuit chip during the chip design process. The invention is more specifically related to a method and apparatus, typically embodied in a CAD system, for selecting and aligning cells on an application specific integrated circuit (ASIC).
The design process for all integrated circuits is composed of several discrete operations. Initially, the proposed functionality for a circuit is analyzed by one or more chip designers. These designers define the logical components of the circuit and their interactions by specifying the logic design using design capture tools. These design capture tools are commonly implemented in software executing on an engineering workstation, with well-known input devices being used to receive design information from the chip designer and output devices, such as computer displays, being used to provide visual feedback of the design to the designer as it is being constructed. Specifically, the design entry operation involves generating a description of the logic design to be implemented on the circuit chip in an appropriate machine-readable form.
Chip designers generally employ hierarchical design techniques to determine the appropriate selection and interconnection of logic and/or memory devices that will enable the chip to perform the desired function. These techniques involve describing the chip""s functionality at various levels of abstraction, ranging from the most general function performed by the chip to the precise functions performed by each logic and/or memory element on the chip.
The hierarchy of a logic design typically has xe2x80x9cNxe2x80x9d levels of functions, where N is an integer (N greater than =1) representing the number of hierarchical levels of functionality in the chip. The first level is typically the chip itself. Each of the lower levels of hierarchy, such as when xe2x80x9cNxe2x80x9d is an integer (1 less than =n less than =N), represent the level of any particular function in the hierarchy. A function consists of a discrete logic and/or memory element, or any combination of such elements. It may be as simple as an inverter or a flip-flop, having one or only a few transistors, or as complex as a shift register, an arithmetic logic unit (ALU), or even a microprocessor.
A parent function at the (N) level of the hierarchy is defined as a plurality of (N+1) level functions, each of which is a child function. For example, a microprocessor at the (N) level might be defined as the parent of the following (N+1) level children: an ALU, a series of registers, a bus, and various other functions (each of which may or may not have a plurality of (N+2) level children, and so on). Each child function which is not also a parent function (i.e., which has no children) is referred to as a leaf function or cell. Each leaf cell in a design is connected to at least one other leaf cell, such connection being commonly referred to as a xe2x80x9cnet.xe2x80x9d The set of nets, each of which often defines a plurality of interconnected functions, is commonly referred to as a xe2x80x9cnetlist.xe2x80x9d
It is useful to distinguish between those cells provided by the chip vendor as primitive cells (i.e., leaf candidates) and the user-defined hierarchy blocks built upon them. One way is to speak of a xe2x80x9ccell libraryxe2x80x9d vs. a xe2x80x9cdesign libraryxe2x80x9d as two separate libraries, both of which are available to subsequent designs. Alternatively, at least initially, a design library contains a standard cell library. A cell library is a database containing detailed specifications on the characteristics of each logical component available for use in a design.
The initial cell library is usually provided by a chip vendor. The components in the cell library are identified by the generic description of the component type. For example, the term xe2x80x9cNANDxe2x80x9d for a NAND gate is its type description and distinguishes this component from others such as OR gates, flip-flops, multiplexors, and so on. A two-input NAND gate might be of type 2NAND. When a particular 2NAND component is specified as part of a given circuit design, it is given an instance name, to distinguish it from all other 2NAND gates used in the circuit. The instance name typically includes the instance names of all parent instances by concatenation when defining the instance in the context of the chip. A single name is sufficient when dealing only in the context of a single user function.
The user-defined blocks can then be used to design larger blocks of greater complexity. The user-defined blocks are typically added to the design library, which grows from the additions of new design modules as the design evolves. The top level of the design hierarchy is often a single block that defines the entire design, and the bottom layer of the hierarchy typically includes leaf cells, the cells (i.e., the logical components) that were originally provided in the cell library.
Two common methods for specifying the design are schematic capture and hardware description languages. The schematic capture method provides a sophisticated user interface that allows a logic circuit to be drawn in graphical form on a computer display. Typically, the design is drawn using symbols from the cell and design libraries.
Encoding the design in a hardware description language (HDL) is a more common design entry technique for specifying modern integrated circuits. Hardware description languages are specifically developed to aid designers in describing a circuit. These languages often contain specific functions and syntax to allow complex hardware structures to be described in a compact and efficient way. Often, the circuit is specified at the register transfer level (also known as a xe2x80x9cbehavior levelxe2x80x9d). The register transfer level description is often specified in terms of relatively small building blocks, the names of which are specified by the circuit designer.
For designs using HDL entry, the generation of a detailed description (or gate-level description) is often accomplished using logic design synthesis software. Logic design synthesis software generates a gate-level description of user-defined input and output logic, and also creates new gate-level logic to implement user-defined logical functions. Constituent parts of new gate-level logic created during each pass through the logic design synthesis software are typically given computer-generated component and net names. Each time the logic design synthesis software is executed, the component and net names that are generated by the software, and not explicitly defined by the user, may change depending on whether new logic has been added to or deleted from the integrated circuit design. Typically, the logic design synthesis software is executed many times during the integrated circuit design process, because errors are detected during the simulation and testing phases of the design cycle and then fixed in the behavioral description.
In some design processes, the output of the logic design synthesis software is optimized by a logic optimizer tool, typically implemented in software. The logic optimizer tool can often create more efficient logic in terms of space, power or timing, and may remove logic from the design that is unnecessary. This action also typically affects the component and net names generated by the logic synthesis tool.
The output of the logic optimizer tool is an optimized detailed description that completely specifies the logical and functional relationships among the components of the design. Once the design has been converted to this form, it is necessary to verify that the logic definition is correct and that the circuit implements the function expected by the designer. If errors are detected or the resulting functionality or timing is unacceptable, the designer modifies the design as needed. As a result of each revision to the design, the logic design synthesis-generated component and net names may again change. These design iterations, however, help ensure that the design satisfies the desired requirements.
After timing verification and functional simulation has been completed on the design, placement and routing of the design""s components is performed. These steps involve assigning components of the design to locations on the integrated circuit chip and interconnecting the components to form nets. This may be accomplished using automated and/or manual place and route tools.
Because automatic placement tools may not yield an optimal design solution, particularly for high performance designs that have strict timing and physical requirements, circuit designers often manually place critical circuit objects (e.g., functions or cells) within the boundary of the integrated circuit. This may be accomplished by using a commercially available placement directive tool (also known as a placement or floorplanning tools), typically implemented in software. The placement tool may include a graphics terminal that provides the circuit designer with visual information pertaining to the circuit design. This information is typically contained in several different windows.
A floorplanning window may display a graphical representation of, for example, the die area of an integrated circuit, the placed objects and connectivity information. Similarly, a placed physical window may display the alphanumeric names of all placed cells and hierarchical functions. An un-placed physical window may display the alphanumeric names of all un-placed cells and hierarchical functions. A logic window may display a hierarchical tree graph of the circuit design.
During the placement process, the circuit designer may select the name of a desired object from the un-placed physical window displaying the un-placed objects. After this selection, the placement tool retrieves the physical representation of the selected object, and the circuit designer uses the cursor to position the physical representation of the selected object within the floorplanning window. The placement tool may then move the alphanumeric name of the selected object from the un-placed physical window to the placed physical window to indicate the placement thereof.
To edit the placement of desired objects, the circuit designer typically selects the desired object from within the floorplanning window using a pointing device. For example, the circuit designer may draw a rectangle around the desired objects to affect the selection. After selection, the circuit designer may instruct the placement tool to perform a desired editing function on the selected objects.
Some placement tools allow the circuit designer to select a desired level of hierarchy or region as the current working environment, or xe2x80x9ccontextxe2x80x9d. When the context is set, all of the objects existing at the next lower level in the circuit design hierarchy are displayed in one of the physical windows, thus making them available for placement or editing. These objects are called children objects of the selected context, and may include other hierarchical objects, including regions and/or cells. Thus, a context may include a mixture of regions and cells.
In this environment, a circuit designer may perform preliminary placement by first placing high level regions. In some placement tools, the outer boundaries of the regions are appropriately sized to accommodate all underlying objects, even though all of the objects may not yet be placed. Thus, the circuit designer may rely on an automated placement tool to subsequently position the underlying objects within the boundary of the region. If more detailed placement is required because of timing, physical or other constraints, selected lower level regions or cells may be manually placed by the circuit designer.
After placement is complete, the routing step must be performed. As mentioned above, a net is a set of points that are to be electrically equivalent by connection. The purpose of routing is to connect points in each net of the logic design so that the connections required within nets are complete. The position of the points in any particular net are decided by the placement process, although there may be sets of points that are already connected together, thereby introducing choices as to where a connection has to be made to complete a net.
Global routing aims to decide exactly which points in each net will be connected together and the approximate path that each connection will take. Fine routing involves determining the final paths of all connections needed to complete the design. Automatic routing by routing tools often requires a large amount of computational effort. The routing problem can be significantly reduced in complexity if a near-optimal placement of the cells has been achieved. It is during this final stage of the physical design of the circuit that the inability to complete the design on a particular sized chip and architecture is detected. This layout failure may have been caused by an unsatisfactory placement. Often, the failure to complete the design is only apparent when the final few percent of the connections are being added. Hence, it is critical that an excellent placement of the cells is generated during the placement process.
In recent years, data paths have become a greater part of many modern chip designs, often consuming over 80 percent of the total circuitry on the chip. Ideally, a placed data path includes a collection of vertical and horizontal wires with logic elements located at the intersections that combine to perform an overall data processing function. While some placement tools attempt to automate part of all of the placement of data path structures, circuit designers can often provide a better solution by manually placing at least some of the cells.
To manually place cells within a data path, it is often desirable to traverse the data path to evaluate the placement of the placed cells and to identify unplaced cells that are part of the data path. To date, traversing such data path structures has been difficult. To identify cells within the data path, the circuit designer typically must manually find each instance name by scanning some external printout, panning through a list of instance names in the placed physical window, or by identifying the physical representation of the cell within the floorplanning window. Each of these has proven to be time consuming and tedious, particularly since many logic design synthesis software programs assign computer generated component and net names.
As a result of these difficulties, circuit designers often only have time to manually place a fraction of the cells within a data path. The remaining cells are placed using automatic placement tools, which typically use algorithms that optimize wire congestion rather than performance or gate density. Accordingly, any improvement in the manual placement process that can significantly reduce the time required to traverse and place cells within a circuit design would be beneficial.
The present invention provides methods and apparatus for efficiently traversing and placing cells in a circuit design. In one illustrative embodiment, one or more leaf cells are identified as base objects. The base objects are placed and aligned along a selected dominate axis, if not already placed and aligned. Once the base objects are identified, an input port can be identified by the circuit designer. In many cases, selected base objects will have at least one common input port identifier, such as xe2x80x9cAxe2x80x9d. By having a common input port identifier, the corresponding input port for each of the selected base objects can be identified. Once identified, the source leaf cells that have an output port that is coupled to the identified input ports can be identified.
As can readily be seen, this may provide an efficient way for a circuit designer to traverse through the various leaf cells and connections of a circuit design. This may be particularly beneficial when analyzing a data path within a circuit design. When the base objects are part of a data path, the identified source leaf cells that drive the identified input ports of the selected base objects are often part of the previous stage of the data path. Thus, a circuit designer can easily trace back through the data path to evaluate the placement of the various cells of the data path. To help place the various cells of a data path, it is contemplated that the identified source leaf cells may be placed and aligned along the dominate axis of the base objects, if desired.
At any time, a different input port name may be selected, identifying a different input port of selected base objects. The tool may then identify the source leaf cells that have an output port that is connected to the identified input ports. Again, the newly identified source leaf cells may be aligned along the dominate axis of the base objects, if desired. This process may continue until all of the leaf cells driving the input ports of the base objects have been identified and/or aligned.
It is contemplated that the source leaf cells that are identified as having an output port connected to a selected input port of selected base objects may be identified as the new base objects. Once selected, the above-described process may be repeated to identify those source leaf cells that drive a selected input port of the new base objects. If desired, the identified leaf cells may be aligned along the dominate axis of the new base objects, as described above. This process may continue until, for example, an entire data path is placed and aligned.
Rather than selecting an input port of selected base objects, it is contemplated that an output port name may be selected. In this case, those destination leaf cells that have an input port that is connected to the selected output ports may be identified and, if desired, aligned along the dominate axis of the base objects. It is contemplated that there may be a qualifier or filter to identify only those destination leaf cells that are, for example, placed. If unplaced destination leaf cells are identified, the present invention preferably places the leaf cells. In some cases, more than one destination leaf cell will be identified for selected base objects. If this occurs, a selected destination leaf cell is selected for each base object. The selected destination leaf cells are then aligned along the dominate axis of the base objects, if desired. The remaining destination leaf cells may be placed adjacent the corresponding selected destination leaf cell and aligned along an axis that is perpendicular to the dominate axis.